1. Field of the Invention
The present invention relates to communication systems, and more particularly, to a method and apparatus for reclaiming memory buffers used for temporary storage of received data in a communication system.
2. Description of the Related Art
Modern communication systems, such as computer networking systems or communication networks, provide constant transmission of data between end stations and/or intermediate stations such as routers and signal amplifiers. Computer networking systems, such as packet switched networks (e.g., Ethernet networks), often require transmission of data to a single end station or to multiple end stations within the network. The data originates from a user program and is segmented into multiple data frames, and subsequently transmitted in order to simplify processing and minimize the retransmission time required for error recovery. For example, in a conventional e-mail system, a user may desire to send the same e-mail message to four different users that are connected to the e-mail system. Accordingly, the identical data would be directed to multiple end stations.
Packet switched computer networks typically employ a network switch that receives and forwards data frames to individual and/or multiple end stations. The network switch makes forwarding decisions upon receipt of data frames based on information contained in a header of the data frame. For example, if a received data frame is to be transmitted to a number of end stations, the switch must make the forwarding decision to forward the data frame to the ports of the correct end stations. Depending on the specific implementation and/or characteristic of the networking system (i.e., data transfer rate, traffic intensity, etc.), buffers must be provided for temporary storage of the data frames, received by the switch, until forwarding decisions can be made. The buffers used to store the data frames are often implemented as first in, first out (FIFO) queues.
In packet switched networks that utilize buffers to temporarily store data frames prior to transmission to the appropriate end station, it is common for the size of an individual data frame to be larger than the capacity of an individual buffer. Buffers are typically allocated a static amount of memory, hence requiring that multiple buffers be used to store a single frame of data that exceeds the buffer""s capacity. Buffering the data as it is received allows, for example, robust error checking to be performed on the data frames, and also permits rate matching between transmitting and receiving ports. When data frames arrives at a network switch, only buffers that are currently available (i.e., xe2x80x9cfreexe2x80x9d) may be used to store the data frames, in order to prevent overwriting of a first data frame by a second data frame prior to transmission. Once the data frames have been transmitted, or is otherwise determined to be no longer necessary, the buffers storing the data frames may be reused to store newly received data frames. In addition, it is possible for buffers to be set aside for storing incoming data frames, but because of error checking or an insufficient amount of data received, the data frames must be discarded. In such circumstances, the buffers must be returned for reuse in order to avoid a potential situation wherein all of the system buffers are improperly set aside to receive data frames that have been discarded.
For purposes of efficiency and continued operation of the network system, it is imperative that buffers be available to store incoming data frames to the extent possible. In addition, the return of the buffers for reuse should be performed as quickly as possible after the buffers are no longer needed.
In systems that employ multiple buffers to store a single data frame, the network switch monitors the transmission of the data frame, and begins the process of reclaiming the individual buffers that store the data frame after the entire data frame has been transmitted. If multiple copies of the same data frame must be transmitted, then the network switch waits until all copies of the data frame have been transmitted before beginning the process of reclaiming the buffers used to store the data frame. Hence, different reclaiming procedures would be more efficient depending on whether a single copy of the frame is transmitted, or multiple copies of the frame are transmitted, and whether the data frame is stored in a single frame buffer or multiple frame buffers.
Accordingly, a primary disadvantage associated with current methods of transmitting data in communication systems, such as a packet switched computer networking system, is the amount of time required to free the buffers that are used to store incoming data frames, once the data frames have been transmitted.
Another disadvantage associated with current methods of transmitting data in communication systems is the inefficiency associated with utilizing the same circuitry (or method) to reclaim buffers regardless of whether a data frame is stored in a single frame buffer or multiple frame buffers.
There is a need for an arrangement and a method for quickly reclaiming buffers that store data frames upon transmission of the data frames so that the buffers can be available to store newly received data frames.
There is also a need for an arrangement and method that distinguishes between single and multiple buffer data frames, and efficiently reclaims buffers depending on whether a data frame is stored in one buffer or multiple buffers.
These and other needs are addressed by the present invention, wherein a multiport switch determines whether a particular data frame is stored in one frame buffer or multiple frame buffers, and places the corresponding frame pointer into either a reclaim queue or a free buffer queue based on such a determination.
In accordance with one aspect of the present invention, an apparatus for reclaiming frame buffers used to store data frames received by a network switch comprises a multicopy queue, a free buffer queue, and a multicopy circuit. The multicopy queue stores entries corresponding to received data frames which must be transmitted to multiple output ports of the network switch. Each entry queued by the multicopy queue includes a frame pointer that addresses a location in memory where frame buffers for storing the received data frames are located. The free buffer queue stores frame pointers that identify locations in the memory where reclaimed frame buffers are located. Each reclaimed frame buffer is available for storing newly received data frames. The multicopy circuit retrieves entries from an output portion of the multicopy queue, and determines if all copies of a received data frame have been transmitted by the multiple output ports. If all copies of the received data frame have been transmitted, then the multicopy circuit reclaims one or more frame buffers based on the size of the received data frame.
The present apparatus efficiently reclaims frame buffers by determining whether a received data frame is stored in one frame buffer or multiple frame buffers. If it is determined that only one frame buffer is used to store the data frame, then the multicopy circuit may place the frame pointer directly into the free buffer queue. If, however, multiple frame buffers are used to store the data frame, then the multicopy queue places the frame pointer in the reclaim queue so that the reclaim queue may use the frame pointer to access the first frame buffer, and walks a linked list of frame buffers in order to free all of the frame buffers used to store the data frame.
According to one specific implementation of the present invention, the multicopy circuit includes a searchable memory area for storing values corresponding to the number of copies of each received data frame that must be transmitted, and a search engine for searching the searchable memory area and updating the values stored therein to reflect the current number of copies of each received data frame that remain to be transmitted. The search engine may be configured to retrieve entries from an output portion of the multicopy queue, decode addresses specified by frame pointers stored in the retrieved entries into corresponding address locations in the searchable memory area, and update the values stored in the searchable memory area based on copy numbers stored in the retrieved entries and the decoded addresses.
The searchable memory area provides a one-to-one correspondence with the total number of frame pointers available to the network switch. This allows the search engine to continually service the multicopy queue and place entries into the searchable memory area.
In accordance with another aspect of the present invention, a method of reclaiming buffers used to store data frames received by a network switch comprises the steps: inputting entries into a multicopy queue that queues entries corresponding to received data frames which must be transmitted to multiple output ports of the network switch, the entries storing frame pointers that address locations in memory where frame buffers that are no longer needed to store received data frames are located; determining if all copies of a received data frame have been output to the multiple output ports; and if all copies of the received data frame have been output to the multiple output ports, then reclaiming one or more frame buffers used for storing the received data frame, based on the size of the received data frame.
The present arrangement provides an efficient method of reclaiming frame buffers based on whether a received data frame is stored in one frame buffer or multiple frame buffers. Accordingly, an appropriate and efficient course of action for reclaiming the frame buffers may be made upon determining the size of the received data frame.
Additional advantages and novel features of the present invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following, or may be learned by practice of the invention. The advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.